Subtree of another tree

Time: O(MxN); Space: O(H); easy

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:

Input: s = {TreeNode} [3,4,5,1,2]

     3
    / \
   4   5
  / \
 1   2

t = {TreeNode} [4,1,2]

   4
  / \
 1   2

Output: True

Explanation:

  • t has the same structure and node values with a subtree of s.

Example 2:

Input: s = [3,4,5,1,2,None,None,None.None,0]

     3
    / \
   4   5
  / \
 1   2
    /
   0

t = {TreeNode} [4,1,2]

   4
  / \
 1   2

Output: False

Hints:

  1. Which approach is better here- recursive or iterative?

  2. If recursive approach is better, can you write recursive function with its parameters?

  3. Two trees s and t are said to be identical if their root values are same and their left and right subtrees are identical. Can you write this in form of recursive formulae?

  4. Recursive formulae can be: isIdentical(s,t)= s.val==t.val AND isIdentical(s.left,t.left) AND isIdentical(s.right,t.right)

1 Using Preorder Traversal

Algorithm

  1. We can find the preorder traversal of the given tree s and t, given by, say s(preorder) and t(preorder) respectively (represented in the form of a string). Now, we can check if t(preorder) is a substring of s(preorder).

  2. But, in order to use this approach, we need to treat the given tree in a different manner.

  3. Rather than assuming a null value for the childern of the leaf nodes, we need to treat the left and right child as a lnull and rnull value respectively.

  4. This is done to ensure that the t(preorder) doesn’t become a substring of s(preorder) even in cases when t isn’t a subtree of s.

  5. You can also note that we’ve added a ‘#’ before every considering every value. If this isn’t done, the trees of the form s:[23, 4, 5] and t:[3, 4, 5] will also give a true result since the preorder string of the t(“23 4 lnull rull 5 lnull rnull”) will be a substring of the preorder string of s(“3 4 lnull rull 5 lnull rnull”). Adding a ‘#’ before the node’s value solves this problem.

See also: https://leetcode.com/problems/subtree-of-another-tree/solution/

2. By Comparison of Nodes [O(M∗N), O(N)]

Algorithm

Instead of creating an inorder traversal, we can treat every node of the given tree tt as the root, treat it as a subtree and compare the corresponding subtree with the given subtree ss for equality. For checking the equality, we can compare the all the nodes of the two subtrees.

For doing this, we make use a function traverse(s,t) which traverses over the given tree ss and treats every node as the root of the subtree currently being considered. It also checks the two subtrees currently being considered for their equality. In order to check the equality of the two subtrees, we make use of equals(x,y) function, which takes xx and yy, which are the roots of the two subtrees to be compared as the inputs and returns True or False depending on whether the two are equal or not. It compares all the nodes of the two subtrees for equality. Firstly, it checks whether the roots of the two trees for equality and then calls itself recursively for the left subtree and the right subtree.

See also: https://leetcode.com/problems/subtree-of-another-tree/solution/

[4]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

[5]:

class Solution1(object):
    """
    Time: O(M*N), M is the number of nodes of s, N is the number of nodes of t
    Space: O(H), H is the height of s
    """
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        def isSame(x, y):
            if not x and not y:
                return True

            if not x or not y:
                return False

            return x.val == y.val and \
                   isSame(x.left, y.left) and \
                   isSame(x.right, y.right)

        def preOrderTraverse(s, t):
            return s != None and \
                   (isSame(s, t) or preOrderTraverse(s.left, t) or preOrderTraverse(s.right, t))

        return preOrderTraverse(s, t)

[7]:

sol = Solution1()

s = TreeNode(3)
s.left, s.right = TreeNode(4), TreeNode(5)
s.left.left, s.left.right = TreeNode(1), TreeNode(2)
t = TreeNode(4)
t.left, t.right = TreeNode(1), TreeNode(2)
assert sol.isSubtree(s, t) == True

s = TreeNode(3)
s.left, s.right = TreeNode(4), TreeNode(5)
s.left.left, s.left.right = TreeNode(1), TreeNode(2)
s.left.right.left = TreeNode(0)
t = TreeNode(4)
t.left, t.right = TreeNode(1), TreeNode(2)
assert sol.isSubtree(s, t) == False